Obeleži sve kategorije koje odgovaraju problemu

Модификовано Ератостеново сито

Често у задацима имамо потребу да извршимо факторизацију више различитих бројева. Такви алгоритми се могу оптимизовати модификацијом Ератостеновог сита која подразумева да се за сваки број запамти неки његов прост чинилац (обично то буде најмањи прост чинилац). Тада се факторизација може извршити тако што се број дели својим најмањим простим чиниоцем (прочитаним из табеле) све док се не сведе на 1.

На пример, бројеви до 50 имају следеће најмање просте чиниоце, који се лако могу одредити Ератостеновим ситом. Прости бројеви су они чији је најмањи делилац једнак самом броју.

 1  2  3  2  5  2  7  2  3  2
11  2 13  2  3  2 17  2 19  2
 3  2 23  2  5  2  3  2 29  2
31  2  3  2  5  2 37  2  3  2
41  2 43  2  3  2 47  2  7  2

Факторизација броја 36 се може одредити тако што се са позиције 36 прочита фактор 2, затим са позиције 18 фактор 2, затим са позиције 9 фактор 3 и на крају са позиције 3 фактор 3.